package com.test.daily.leetcode.y2022.m05.day0526.v03;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/26 下午 07:05
 * @version: 1.0
 */
public class Solution {
    public static class UnionFind<V> {
        // parent[i] = k, i的父親是k
        public int[] parent;
        // size[i] 節點i的集合大小
        // i節點要有意義
        public int[] size;
        // 集合大小
        public int sets;
        // help數組, 類似於存儲中間變量
        public int[] help;

        public UnionFind(V[] list) {
            int N = list.length;
            help = new int[N];
            sets = N;
            parent = new int[N];
            size = new int[N];
            for (int i = 0; i < N; i++) {
                size[i] = 1;
                parent[i] = i;
            }
        }

        public int findFather(int i) {
            int hi = 0;
            while (parent[i] != i) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi++) {
                parent[help[hi]] = i;
            }
            return i;
        }

        public void union(int i, int j) {
            int iHead = findFather(i);
            int jHead = findFather(j);
            if(iHead != jHead){
                if(size[i] > size[j]){
                    parent[jHead] = iHead;
                    size[iHead] += size[jHead];
                } else {
                    parent[iHead] = jHead;
                    size[jHead] += iHead;
                }
                sets--;
            }
        }
        public int sets(){
            return sets;
        }
    }
}
